1. Field of the Invention
The present invention relates to a method and apparatus for searching a forwarding table, and more particularly, to a method and apparatus for searching a forwarding table capable of effectively searching for and managing forwarding information for allowing a network switch to transmit a frame to a desirable port among a plurality of ports.
This work Was supported by the IT R&D program of MIC/IITA[2005-S-102-02, Carrier Class Ethernet Technology].
2. Description of the Related Art
A network switch included in a communication network needs a forwarding searching engine and address translation mechanism so as to receive data from another network equipment and transmit the data to a desirable port.
Since the performance of the network switch is largely influenced by a speed of determining a forwarding path, the efficiency and the speed of the forwarding searching engine and the address translation mechanism are main factors for determining the performance of the network switch.
In general, in order to reduce a searching time, the network switch includes a hash unit for transforming a search key having a large number of bits into an index value having a small number of bits. Accordingly, it is possible to acquire an appropriate forwarding entry by searching the forwarding table with the hash index of less length than the original search key.
FIG. 1 illustrates a concept of an operation of an apparatus for searching a forwarding table according to a conventional example. The apparatus for searching the forwarding table of FIG. 1 selects a forwarding entry fwd_ent in a forwarding table fwd_table and compares a media access control (MAC) address of the selected entry with an input MAC address. When the MAC address of the selected entry is the same as the input MAC address, output port information of the selected forwarding entry fwd_ent is read. Otherwise, the MAC address of the next forwarding entry fwd_ent sequentially is compared with the input MAC address to obtain the output port information.
At this time, the forwarding entries are not aligned based on a predetermined rule but aligned in the order to storing the forwarding entries.
Accordingly, in this sequential searching method, since information of all the forwarding entries fwd_ent has to be read and compared, it takes too much time to determine a forwarding path.
In order to complement this disadvantage, in U.S. Pat. No. 6,266,705, as shown in FIG. 2, a method of searching for an appropriate forwarding entry and sorting a plurality of forwarding entries into several pages by using a dual hashing technique is suggested.
In a method of FIG. 2, a page to be searched by using the most significant bits (MSB) of 3 bits of a hash key is firstly selected, and forwarding entries in the page are sequentially searched.
Accordingly, in the method of FIG. 2, the searching time is largely reduced as compared with the existing sequential searching method. However, the searching speed decreases in proportion to the number of forwarding entries included in the page.